class Solution
{
public:
    // 官方给的提示和答案是两种不同的方法，都很巧妙

    // 提示的方法：用公式求1到n的和、平方和，减去已有元素，得到方程组
    vector<int> missingTwo(vector<int> &nums)
    {
        int len = nums.size();
        long long n = len + 2;
        long long linearSum = n * (n + 1LL) / 2LL;
        long long squareSum = n * (n + 1LL) * (2LL * n + 1LL) / 6LL;
        for (int num : nums)
        {
            linearSum -= num;
            squareSum -= num * num;
        }
        long long a = 2LL;
        long long b = -2LL * linearSum;
        long long c = linearSum * linearSum - squareSum;
        int root1 = static_cast<int>((-b - sqrt(b * b - 4 * a * c)) / 2.0 / a);
        int root2 = static_cast<int>((-b + sqrt(b * b - 4 * a * c)) / 2.0 / a);
        return {root1, root2};
    }

    // 位运算
    vector<int> missingTwo(vector<int> &nums)
    {
        int xorsum = 0;
        int n = nums.size() + 2;
        for (int num : nums)
        {
            xorsum ^= num;
        }
        for (int i = 1; i <= n; i++)
        {
            xorsum ^= i;
        }
        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num : nums)
        {
            if (num & lsb)
            {
                type1 ^= num;
            }
            else
            {
                type2 ^= num;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            if (i & lsb)
            {
                type1 ^= i;
            }
            else
            {
                type2 ^= i;
            }
        }
        return {type1, type2};
    }
};